/*
 * @lc app=leetcode.cn id=141 lang=javascript
 *
 * [141] 环形链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/** 环形链表
 * 快慢指针：一快一慢指针遍历链表
 * 1. 如果有环，两个指针肯定有相等的情况
 * 2. 如果没有环，快指针会先跑到null从而终止循环
 * 时间复杂度：n；空间复杂度：13
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let p1 = head;
  let p2 = head;
  while (p1 && p2 && p2.next) {
    p1 = p1.next;
    p2 = p2.next.next;
    if (p1 === p2) {
      return true;
    }
  }
  return false;
};
// @lc code=end
